/*Compile with: 
$ g++  -I$HOME/sw/include main.c -o main  -L$HOME/sw/lib -lntl  -lm
*/


#include <fstream>

#include <math.h>
#include <NTL/ZZ_pXFactoring.h>
#include <NTL/ZZ_pEX.h>

#include <NTL/matrix.h>
#include <NTL/vec_vec_ZZ_pE.h>
#include <NTL/mat_ZZ_pE.h>
#include <NTL/mat_GF2.h>
#include <NTL/mat_ZZ_p.h>
#include <NTL/ZZ_pEXFactoring.h>

#include "SQ_ZZ_pEXFactoring.h"
#include "SQ_ring.h"
#include "tools.h"

#define DEBUG 0

NTL_CLIENT

char filename[50];
ofstream myfile;

void translate_to_latex(ZZ_pEX a,vec_ZZ_pE element)
{
	int poly_deg = (int) deg(a);

myfile.open(filename,ios_base::app);

	if(!IsZero(coeff(a,0)) )
	{
		if(coeff(a,0) == element[1])
			myfile << "1 ";
		else if(coeff(a,0) == element[2])
			myfile << "\\alpha ";
		else
			myfile << "\\alpha^{2} ";
		myfile  << " + ";		
	}
	
	for(int i=1;i<poly_deg;i++)
	{
		if(!IsZero(coeff(a,i)) )
		{
			if(coeff(a,i) == element[1])
				myfile << " ";
			else if(coeff(a,i) == element[2])
				myfile << "\\alpha ";
			else
				myfile << "\\alpha^{2} ";
			myfile  << "x^{" << i << "} + ";		
		}
	}

		if(!IsZero(coeff(a,poly_deg)) )
		{
			if(coeff(a,poly_deg) == element[1])
				myfile << " ";
			else if(coeff(a,poly_deg) == element[2])
				myfile << "\\alpha ";
			else
				myfile << "\\alpha^{2} ";
			myfile  << "x^{" << poly_deg << "} ";		
		}

myfile.close();

}


/**
 * generates elements of GF(4)
 *
 * @return number of elements of the field
 **/
long generate_GF4(vec_ZZ_pE& element)
{	
	long num_of_elements = to_long(ZZ_pE::cardinality());
	element.SetLength(num_of_elements);
	clear(element[0]); // element[0] = 0
	set(element[1]); // element[1] = 1
	//element[2] = alpha;
	for(int i=3; i<num_of_elements;i++)
		element[i]=element[i-1]*element[2];

	return num_of_elements;
}

long MYgenerate_GF4(vec_ZZ_pE& element)
{	
	ZZ_pE alpha;

	char str1[256],str2[256];	// inefficient way of generating the primitive element
	ifstream In_tempfile;
	In_tempfile.open("primitive_element.ntl");
        In_tempfile.getline(str1,256);
	In_tempfile.close();
//cout << "given: " << str1 << endl;
//fflush(stdout);

	while(1)
	{
	         alpha = random_ZZ_pE();
		 if( !IsZero(alpha) && !IsOne(alpha) ) 
		{
			ofstream tempfile;
			tempfile.open("primitive.element");
			tempfile << alpha << endl;
			tempfile.close();

			ifstream tempfile1;
			tempfile1.open("primitive.element");
			tempfile1.getline(str2,256);
			tempfile1.close();			
//cout << "str2: " << str2 << endl;
			if(!strcmp(str1,str2))
				break;
		}
	}
//cout << "alpha: " << alpha <<  endl;

	long num_of_elements = to_long(ZZ_pE::cardinality());
	element.SetLength(num_of_elements);
	clear(element[0]); // element[0] = 0
	set(element[1]); // element[1] = 1
	element[2] = alpha;
	for(int i=3; i<num_of_elements;i++)
		element[i]=element[i-1]*element[2];

	return num_of_elements;
}

/**
 * Generates a list of messages of length k with weight j with elements in GF(q)
 *
 * This function considers all possibilities in terms of all the elements in GF(q)
 *
 * @list list of vectors, Note: memory must be preallocated for the list of size [k choose j,k]
 * @k	length of messages 
 * @j	weight
 *
 * @return size of the list
 *
 **/
int micro_msg_generator(vec_ZZ_pE* list,int k,int j,int horizontal_index=0,int vertical_index=0)
{
//cout << "micro call" << endl;
	vec_ZZ_pE element;
	long num_of_elements = MYgenerate_GF4(element);

	if(j>k || j==0)
		return vertical_index;
	else if( j==1 && k==1 )
	{
		for(int m=1;m<num_of_elements;m++)
		{
			list[vertical_index][horizontal_index]= element[m]; // set element to 1
			vertical_index++;
		}
		return vertical_index;
	}

	for(int m=1;m<num_of_elements;m++)
	{
		micro_msg_generator(list,k-1,j-1,horizontal_index+1,vertical_index);
		int vertical_stop_index = vertical_index + pow( (double) (num_of_elements-1), (double) (j-1))*nChoosek(k-1,j-1);
		for(;vertical_index<vertical_stop_index;vertical_index++)
		{
				list[vertical_index][horizontal_index]=element[m];
//cout << "micro= " << list[vertical_index] << endl;
		}
	}
	return micro_msg_generator(list,k-1,j,horizontal_index+1,vertical_index);

}


/**
 * Generates a list of messages of length k with weight j
 * 
 * This function is a helper function that fills in the leading elements by 1 and calls
 * micro_msg_generator() to take care of covering for other elements in GF(q)
 *
 * @list list of vectors, Note: memory must be preallocated for the list of size [k choose j,k]
 * @k	length of messages 
 * @j	weight
 *
 * @return size of the list
 *
 **/
int qarry_msg_generator(vec_ZZ_pE* list,int k,int j,int horizontal_index=0,int vertical_index=0)
{

	vec_ZZ_pE element;
	long num_of_elements = MYgenerate_GF4(element);

	if(j>k || j==0)
		return vertical_index;
	else if( j==1 && k==1 )
	{
//		list[0].SetLength(k);
		list[vertical_index][horizontal_index]=element[1];
		return(vertical_index+1);
	}
	
	int kChoosej= nChoosek(k,j);
	int stop_vertical_index = vertical_index+(kChoosej* pow( (double) (num_of_elements-1), (double) (j-1) ));

	// allocate memory
//	list = new vec_ZZ_pE [stop_vertical_index];
//	for(int i=0;i<stop_vertical_index;i++)
//		list[i].SetLength(k);


	while(vertical_index < stop_vertical_index)
	{
		micro_msg_generator(list,k-1,j-1,horizontal_index+1,vertical_index);
		int stop_index = vertical_index+(nChoosek(k-1,j-1)* pow( (double) (num_of_elements-1), (double) (j-1) ));
		for(;vertical_index<stop_index;vertical_index++)
{
			list[vertical_index][horizontal_index]=element[1];
//cout << list[vertical_index] << endl;
}

		horizontal_index++;	
		k--;
	}
	return vertical_index;
}


int generate_int(int*& element,int low,int high)
{
	int size = high-low+1;
	element = new int [size];
	int low_CPY = low;
	int i;
	for(i=0;low_CPY<=high;low_CPY++,i++)
	{
		element[i] = low_CPY;
//		cout << element[i] << endl;
	}

	return i;
}

int LDPC_coeff_generator(int**& list,int k,int low,int high,int horizontal_index=0,int vertical_index=0)
{

	int* element;
	int num_of_elements = generate_int(element,low,high);

	if(k==0)
		return vertical_index;
	else if(k==1 )
	{
//		list[0].SetLength(k);
		for(int i=0;i<num_of_elements;i++)
		{
			list[vertical_index][horizontal_index]=element[i];
			vertical_index++;
		}
		return vertical_index;
	}
	
	for(int m=0;m<=num_of_elements-k;m++)
	{
		int vertical_stop_index = LDPC_coeff_generator(list,k-1,element[m]+1,high,horizontal_index+1,vertical_index);

//		int vertical_stop_index = vertical_index + pow( (double) (num_of_elements-1), (double) (j-1))*nChoosek(k-1,j-1); // ?????

		for(;vertical_index<vertical_stop_index;vertical_index++)
		{
				list[vertical_index][horizontal_index]=element[m];
		}
	}
	return vertical_index;
}


/**
 * Fast algorithm to find the minimum distance of a cyclic code given an skew generator polynomial.
 *
 * The algorithm is based on the Kschischang-Pasupathy method and has 3 options.
 *
 * @ref: "Some Ternary and Quaternary Codes and Associated Sphere Packings", F. R. Kschischang, S. Pasupathy, IEEE Transactions on Information Theory, vol 38, NO 2, March 1992
 * 
 * @gen_poly	the generator polynomial in skew polynomial ring with Frobenius Automorphism
 * @n	code length as in classical form [n,k]-code
 * @select =0 (default), each tested message (information bits) has 1 as leading non-zero bit (e.g. [0 1 alpha 0 alpha^2] where alpha is primitive element in GF(4))
 * @select =1, messages are in binary (e.g. [0 1 0 1]); 
 * @select =2, messages are from GF(q) (e.g. [0 alpha 1 0 alpha^2] where alpha is primitive element in GF(4)).   
 * @printf_log if set to 1, then function prints log information of the process
 *
 * @return computed minimum distance d
 * 
 **/
int KP_cyclic_dmin(const ZZ_pEX& gen_poly,int n,int select=0,int print_log=0)
{
	// parameters: j={1,...,d_min},Uj, and Lj=ceil((n/k)(j+1))
	int j=0,U_j=n,L_j=0;
	int r = deg(gen_poly);	
	int k = n-r; // following classical notation for a code: [n,k,d_min]-code
	double rate = n/k;
	
	/******************* Print Log ***************************/	
	if(print_log)
	{
		cout << "n: " << n << endl;
		cout << "k: " << k << endl;
		cout << "rate: " << rate << endl;
	}
	/******************* Print Log ***************************/

	// make generator matrix
	mat_ZZ_pE gen_matrix = SQ_gen_matrix(gen_poly,n);

	/******************* Print Log ***************************/	
	if(print_log)
	{
		cout << "Generator Matrix: " << endl << gen_matrix << endl;
	}
	/******************* Print Log ***************************/

	// turn the generator matrix into systematic form
	gauss(gen_matrix);
	reduced_row_echelon(gen_matrix,to_long(ZZ_pE::cardinality()),1);

	/******************* Print Log ***************************/	
	if(print_log)
	{
		cout << "Systematic Form of Generator Matrix: " << endl << gen_matrix << endl;
	}
	/******************* Print Log ***************************/

	// min distance calculation	
	// flip j bits and find Uj for each iteration
	// stop when Lj >= Uj
	while(1)
	{
		j++;
		L_j = (int) ceil(rate*(j+1));

		/******************* Print Log ***************************/	
		if(print_log)
		{
			cout << "@ j= " << j << endl;
			cout << "@ L_j= " << L_j << endl;
		}
		/******************* Print Log ***************************/

		int num_of_msgs;
		vec_ZZ_pE* list;

		// create a list of W_i's of weight j, i.e. j information bits are 1
		if(select ==1)
		{
			int kChoosej= nChoosek(k,j);
			list= new vec_ZZ_pE [kChoosej];	// alocate memory
			for(int i=0;i<kChoosej;i++)
				list[i].SetLength(k);
			num_of_msgs = binary_msg_generator(list,k,j);
		}
		else if(select == 2)
		{
			int kChoosej= nChoosek(k,j);
			long temp = pow((double) digit(ZZ_p::modulus(),0) , (double) ZZ_pE::degree() );
			temp = pow( (double) (temp-1), (double) j);
			list = new vec_ZZ_pE [kChoosej * temp ];
			for(int i=0;i<kChoosej*temp;i++)
				list[i].SetLength(k);
			num_of_msgs=micro_msg_generator(list,k,j);
		}
		else 
		{
			int kChoosej= nChoosek(k,j);
			long temp = pow((double) digit(ZZ_p::modulus(),0) , (double) ZZ_pE::degree() );
			temp = pow( (double) (temp-1), (double) (j-1));
			list = new vec_ZZ_pE [kChoosej * temp ];
			for(int i=0;i<kChoosej*temp;i++)
				list[i].SetLength(k);
			num_of_msgs=qarry_msg_generator(list,k,j);

//for(int i=0;i<kChoosej*temp;i++)
//cout << list[i] << endl;

		}

		// traverse through the list of W_i's and find the minimum weight in each case
		// break if Uj<=Lj
		for(int m=0;m<num_of_msgs;m++)
		{
			vec_ZZ_pE x;
			mul(x,list[m],gen_matrix); // x = list[j]*gen_matrix
			
			int weight = coeff_weight(x);
			if(weight < U_j)
			{
				U_j = weight; // update U_j
				/******************* Print Log ***************************/	
				if(print_log)
				{
					cout << "U_j: " << U_j << endl;
				}
				/******************* Print Log ***************************/
			}
		}
		if(L_j >= U_j) 
		{
			// clear memory
			delete [] list;
			break;
		}
	}

	return U_j;
}

/**
 * Computer search for sparse parity check polymonial of a given weight for x^{n}-1 in GF(2^{m})
 *
 **/
void SQ_find_LDPC(long n,long k,long h_weight)
{
	// generate elements of GF(4)
	vec_ZZ_pE element;
	long num_of_elements = MYgenerate_GF4(element);

//cout << "alpha= " << element[2] << endl;

	// generate x^n-1
	ZZ_pEX f;
	SetCoeff(f,n);		
	SetCoeff(f,0);

myfile.open(filename,ios_base::app);
myfile << "$f(x)=";
myfile.close();
translate_to_latex(f,element);
myfile.open(filename,ios_base::app);
myfile << "$ \\\\" << endl << endl;
myfile.close();

	// generate list of possible coefficients
	vec_ZZ_pE* list_of_coeffs;
	long temp = pow((double) digit(ZZ_p::modulus(),0) , (double) ZZ_pE::degree() );
	temp = pow( (double) (temp-1), (double) (h_weight-2));
	list_of_coeffs = new vec_ZZ_pE [temp];
	for(int i=0;i<temp;i++)
		list_of_coeffs[i].SetLength(h_weight-2);
//	qarry_msg_generator(list_of_coeffs,h_weight-2,h_weight-2);
	micro_msg_generator(list_of_coeffs,h_weight-2,h_weight-2);
	int size_of_alphabet = temp;

	// generate list of possible intermediate power places
	int size=1;
	int high=k-1;
        int low=1;
	for(int i=0;i<h_weight-2;i++)
		size*=(high-i);
  
	int** list_of_places;
	list_of_places = new int* [size];
	for(int i=0;i<size;i++)
		list_of_places[i] = new int [h_weight-2];

	size =  LDPC_coeff_generator(list_of_places,h_weight-2,low,high);

	// search for h(x)
	for(int i=0;i<size;i++)
	{
		for(int m=1;m<num_of_elements;m++)
		{
			for(int j=0;j<size_of_alphabet;j++)
			{
//cout << "coeffs= " << list_of_coeffs[j] << endl;
				// generate template h(x)
				ZZ_pEX h;
				SetCoeff(h,0,element[m]);
				SetCoeff(h,k);
				for(int t=0;t<h_weight-2;t++)	// set coefficients of h(x) in places specified by list_of_places[][] with elements from list_of_coeffs[]
					SetCoeff(h,list_of_places[i][t],list_of_coeffs[j][t]);
				// test if h(x) left devides f(x)
				ZZ_pEX g,R;
//cout << h << endl;
				SQ_divl(f,h,g,R);
				if( IsZero(R) )
				{
					//cout << "h= " << h << endl;
myfile.open(filename,ios_base::app);
myfile << "$g(x)=";
myfile.close();
translate_to_latex(g,element);
myfile.open(filename,ios_base::app);
myfile << "$ \\\\" << endl << "$h(x)=";
myfile.close();
translate_to_latex(h,element);
					//cout << "d_{min}= " << KP_cyclic_dmin(g,n,1,0) << endl;
int dmin = KP_cyclic_dmin(g,n,0,0);
myfile.open(filename,ios_base::app);
myfile << "$ \\\\" << endl << "wt($h(x)$)$= " << h_weight << "$, wt($g(x)$)$= " << coeff_weight(g) << "$,$d_{min}=" << dmin << "$ \\\\" << endl << endl;
myfile.close();
				}
			}
		}	
	}
}

int main()
{

   ZZ_p::init(to_ZZ(2)); // define GF(17)

   ZZ_pX P;
   BuildIrred(P, 2); // generate an irreducible polynomial P
                      // of degree 10 over GF(17)

   ZZ_pE::init(P); // define GF(17^10)
 
   ZZ_pEX f,g,Q,R;

//   ZZ_pE alpha;
//   cin >> alpha;
   
// finding sparse h(s)

   for(int n=8;n<=50;n=n+2)
   {
cout << "--------------------------------------------------------" << endl;
cout << "         n  = " << n << endl;
cout << "--------------------------------------------------------" << endl;

	int k = n/3;

	 sprintf(filename,"d0LDPCn%d.tex",n);
	 myfile.open(filename);
	 myfile << "\\section{ n= $" << n << "$, k=$" << k <<"$}" << endl << endl;
	 myfile.close();


	for(int h_weight=2;h_weight<=5;h_weight++)
	{
cout << "*****  wt(h)= " << h_weight << endl;
		  SQ_find_LDPC(n,k,h_weight);
	}
   }

  
/*
// generat list of int's    
    int j,low,high;
    cout << "j: ";
    cin >> j;
    cout << "low: ";
    cin >> low;
    cout << "high: ";
    cin >> high;
    int size=1;
    for(int i=0;i<j;i++)
        size*=(high-i);
  
    int** list;
    list = new int* [size];
    for(int i=0;i<size;i++)
    {
	list[i] = new int [j];
    }
    size =  LDPC_coeff_generator(list,j,low,high);
    for(int i=0;i<size;i++)
    {
	for(int k=0;k<j;k++)
    		cout << list[i][k] << " ";
	cout << endl; 
    }
*/

/*
// left divide
   long n;
   cout << "n: ";
   cin >> n;

   SetCoeff(f,n);		
   SetCoeff(f,0);

   cout << "g: ";
   cin >> g;

   SQ_divl(f,g,Q,R);
  cout << "f: " << f << endl;
  cout << "g: " << g << endl;
  cout << "Q: " << Q << endl;
  cout << "R: " << R << endl;
  cout << "gQ+R= " << SQ_mulr(g,Q)+R << endl;
*/

// cout << "alpha: ";
// ZZ_pE alpha;
// cin >> alpha;

  // ZZ_pE roots = FindRoot(f);
//   for(int i=0;i<roots.length();i++)
	//cout << roots << endl;

//cout << ZZ_pE::cardinality() << endl;
//   cout << digit(ZZ_p::modulus(),0) << endl;
// cout << ZZ_pE::degree() << endl;

/*
mat_ZZ_pE A;
cout << "enter A: ";
cin >> A;
reduced_row_echelon(A);
cin >> A;
*/

/*
  
   ZZ_pE one;
   set(one);
   ZZ_pEX f = ZZ_pEX((lon	g) 4,one);
   SetCoeff(f,0,one);
   cout << "f: " << f << endl;
*/

//   cout << "g: ";
//   cin >> g;

//   cout <<  ZZ_pEX SQ_power(g,10) << endl;;


/*
// finding d_min
   long n;
   cout << "n: ";
   cin >> n;

   cout << "generator: ";
   cin >> f;

//   cout << "gen Matrix:" << endl << SQ_gen_matrix(f,n) << endl;
	
//   cout << "sel=0 d_min: " <<    KP_cyclic_dmin(f,n) << endl;
   cout << "sel=1 d_min: " <<    KP_cyclic_dmin(f,n,1) << endl;
*/

/*
// generating all messages of weight j and size k 
int j,k;
cout << "k: ";
cin>> k;
cout << "j: ";
cin >> j;
int kChoosej= nChoosek(k,j);
long temp = pow((double) digit(ZZ_p::modulus(),0) , (double) ZZ_pE::degree() );
temp = pow( (double) (temp-1), (double) (j-1));
cout << "number of elements in extension: " << temp << endl;
vec_ZZ_pE list[kChoosej * temp ];
//vec_ZZ_pE* list;
for(int i=0;i<kChoosej*temp;i++)
	list[i].SetLength(k);

   qarry_msg_generator(list,k,j);
//	  micro_msg_generator(alpha,list,k,j);
     for(int i=0;i<kChoosej*temp;i++)
	cout << list[i] << endl;
*/

/*
// heuroistic factorization
//	int n = (int) deg(f);

   long n;
//   cout << "n: ";
   cin >> n;

	SetCoeff(f,n);
	SetCoeff(f,0);	// f = 1+x^{n}
//cout << "f: " << f << endl;


	int dim_of_W = n*2;
	int p,mu;
	p=mu=2;
	// theta = primitive element
	ZZ_pE theta = random_ZZ_pE();
	while( IsZero(theta) || IsOne(theta) )
		theta = random_ZZ_pE();
	theta = power(theta,(long) p*mu);	// non-efficient way of geerating the primitive element using x^{p*mu}=theta, x!=0,1
//cout << endl << "alpha: " << theta << endl;

// create list of elements
vec_ZZ_pE element;
 MYgenerate_GF4(element,theta);


cout << "\\[" << endl;
cout << "\\text{f}(x)=";
translate_to_latex(f,element);
cout << endl << "\\]" << endl;



	// create extension field F with primitive element \theta
	ZZ_pEX W[dim_of_W];
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<mu;j++)
		{
			W[i*mu+j] = ZZ_pEX(i,power(theta,j)); // \theta^{j}x^{i}
//cout << W[i*mu+j] << endl;
		}
	}	
//	cout << "enter deg of factor: ";
	int fac_deg;
	cin >> fac_deg;

       int max_fac_deg = fac_deg;
       fac_deg= fac_deg;
for(;fac_deg<=max_fac_deg;fac_deg++)
{
	cout << endl << endl << "\\section{ $n=" << n << "$ , $r=" << fac_deg  << "$ }"<< endl << endl; 

	vec_ZZ_p coeff_vec;
	coeff_vec.SetLength(dim_of_W);	

	ZZ_p p_ONE;
	set(p_ONE); // p_ONE = 1
	for(int i=0;i<mu*fac_deg;i++)	// only calculate factors after given degree
		coeff_vec[i]= p_ONE;

//cout << coeff_vec << endl;

//cout << "vec of coeff: " << coeff_vec << endl;

//cout << "mu*fac: " << mu*fac_deg << endl;
//cout << "1: " << pow((double) 2,(double) mu*fac_deg) << endl;
//cout << "2: " << pow((double) 2,(double) mu)-1 << endl;

	long num_of_iterations = power_long(2,mu*fac_deg)*(power_long(2,mu)-1)/4;
//cout << "num of iterations " << num_of_iterations << endl;
	int num_of_potentials=0;
	for(int i=0;i<num_of_iterations;i++)
	{
		ZZ_pEX poly;
		coeff_vec = binary_inc(coeff_vec);
		if( IsZero(coeff_vec[0]) && IsZero(coeff_vec[1]) )	// don't consider the case of zero constant coefficient
			coeff_vec = binary_inc(coeff_vec);
//cout << coeff_vec << endl;
		for(int j=0;j < dim_of_W;j++)
			poly+= coeff_vec[j]*W[j];

//cout << poly << endl;
		// test if poly divides f
		SQ_divr(f,poly,Q,R);
		if(IsZero(R))
		{
			int w_of_h = coeff_weight(Q);
			int w_of_g = coeff_weight(poly);			
        	  if(w_of_h < w_of_g)
		  {
//			cout << "f = (" << Q << ")(" << poly << ") + (" << R << ")" << endl;
			cout << "\\[" << endl;
			cout << "\\text{h}(x)=";
			translate_to_latex(Q,element);
			cout << endl << "\\]" << endl;
			cout << "\\[" << endl;
			cout << "\\text{g}(x)=";
			translate_to_latex(poly,element);
			cout << endl << "\\]" << endl;
				
			cout << "weight h $=" << w_of_h << "$, weight g $=" <<  w_of_g << "$, " << endl;
			cout << "$d_{min}=$ $" << KP_cyclic_dmin(poly,n,1,0) << "$ \\\\ " << endl << endl << endl;
			//if(w_of_h<w_of_g)
			//{
				num_of_potentials++;
			//}
		   }	
		}
//cout << coeff_vec << endl;		
	}
}
//	cout << "num of potentials: " << num_of_potentials << endl;
*/

/*
// SQ poly factorization
 ZZ_pEX b1,b2,h;
 int status = SQ_Giesbretch_fac(f,2,2,b1,b2);
cout << "status: " << status << endl;
cout << "b1: " << b1 << endl;
cout << "b2: " << b1 << endl;
if( status > 0 )
{
 h=SQ_gcrd(f,b1);
 SQ_divr(f,h,Q,R);
 cout << f << " = (" << Q << ")(" << h << ") + (" << R << ")" << endl;
 h=SQ_gcrd(f,b2);
 SQ_divr(f,h,Q,R);
 cout << f << " = (" << Q << ")(" << h << ") + (" << R << ")" << endl;
}
*/

/*
// heroistic to find zero divisors
ZZ_pEX garr[6];
for(int i=0; i<6; i++)
{
cout << i << ": ";
cin >> garr[i];
}
for(int i=0;i<6;i++)
{
for(int j=i;j<6;j++)
{
cout << i << "," << j << endl;
ZZ_pEX res = SQ_mulr(garr[i],garr[j]);
cout << "res: " << res << endl;
SQ_divr(res,f,Q,R);
cout << "Q: " << Q << endl;
cout << "R: " << R << endl;

res = SQ_mulr(garr[j],garr[i]);
cout << "res: " << res << endl;
SQ_divr(res,f,Q,R);
cout << "Q: " << Q << endl;
cout << "R: " << R << endl;

cout << "--------------------------------" << endl;
}
}
*/

/*
// divisibility
while(1)
{
   cout << "g: ";
   cin >> g;
   SQ_divr(f,g,Q,R);
   cout << "Q: " << Q << endl;
   cout << "R: " << R << endl;
}

*/

 /*  cout << "g: ";
   cin >> g;

   cout << "f*g: " << SQ_mulr(f,g) << endl;
   cout << "g*f: " << SQ_mulr(g,f) << endl;
*/

/*
// fg mod f
while(1)
{
   cout << "g: ";
   cin >> g;

   g= SQ_mulr(f,g);
   SQ_divr(g,f,Q,R);

   cout << "R: " << R << endl;

}
*/
/*
// finding Kernel
mat_GF2 T,X;
cout << "T: " << endl;
cin >> T;

kernel(X,T);
cout << "T: " << endl << T << endl;
cout << "X: " << endl << X << endl;
*/



// finding minimal poly
/*
cout << "k: " ;
int k;
cin>> k;
cout << "module g: ";
cin >> g;
for(int i=0; i<=k;i++)
{
	ZZ_pEX res  = SQ_power(f,i);
	cout << i << ": " << res << endl;	
	SQ_divr(res,g,Q,R);
	cout << "R: " << R << endl;
}
*/


/*
// powers of b \in K-algebra
ZZ_pEX p2,p4,p6;
p2 = SQ_power(g,k);
cout << "p(x)^2: " << endl << p2 << endl;
SQ_divr(p2,f,Q,R);
cout << "R: " << R << endl;
p4 = SQ_mulr(p2,p2);
cout << "p(x)^2^2: "  << endl  << p4 << endl;
SQ_divr(p4,f,Q,R);
cout << "R: " << R << endl;
p6 = SQ_mulr(p2,p4);
cout << "p(x)^2^3: "  << endl  << p6 << endl;
SQ_divr(p6,f,Q,R);
cout << "R: " << R << endl;
*/
//  random(g,g_deg);
//  random(f,f_deg);


return 0;
}










